package 题目集.数学;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/* 双模幂运算：https://leetcode.cn/problems/double-modular-exponentiation/description/?envType=daily-question&envId=2024-07-30*/
public class 快速幂 {

    public List<Integer> getGoodIndices(int[][] variables, int target) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < variables.length; i++) {
            int pow = pow(variables[i][0], variables[i][1], 10);
            int res=pow(pow,variables[i][2],variables[i][3]);
            if (res== target) {
                result.add(i);
            }
        }
        return result;
    }

    public int pow(int a, int b, int mod){
        int res = 1;
        int temp=a;
        while(b>0){
            if(b%2!=0){
                res = (res*temp)%mod;
            }
            temp = (temp*temp)%mod;
            b/=2;
        }
        return res;
    }


    @Test
    public void test() {
        int[][] variables = {{30,5,43,2},{15,50,35,41},{45,34,41,32},{14,37,33,13},{6,8,1,53},{37,1,12,52},{42,37,2,52},{9,2,15,3},{31,12,21,24},{52,24,6,12},{51,35,21,52},{30,18,10,2},{27,31,50,27},{29,25,26,32},{15,38,43,17},{22,12,16,43},{48,9,15,6},{41,26,22,21},{41,49,52,26},{53,38,9,33}};
        int t=1;
        List<Integer> goodIndices = getGoodIndices(variables, t);
        System.out.println(goodIndices);
    }
}
